package leetcode_core.leetcode_3;

import java.util.Arrays;
import java.util.Comparator;

public class RemoveCoveredIntervals {

    public int removeCoveredIntervals(int[][] intervals) {
        //对起点进行排序哈,从小到大,起点相同时按照降序排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]){
                    return o2[1]-o1[1];
                }
                return o1[0]-o2[0];
            }
        });
        //记录合并区间的起点和终点
        int left = intervals[0][0];
        int right = intervals[0][1];
        int ans = 0;
        for(int i = 1;i<intervals.length;i++){
            int intv[] = intervals[i];
            //情况1:我们找到一个覆盖区间
            if(left<=intv[0] && right>=intv[1]){
                ans++;
            }
            //情况2:找到一个相交的区间,重叠的(也就是这个区间的起点比对标区间的终点要早)
            if(right>= intv[0] && right<=intv[1]){
                right = intv[1];
            }
            //情况3:完全不相交
            if(right < intv[0]){
                left = intv[0];
                right = intv[1];
            }
        }
        return intervals.length-ans;
    }


}
